package base_Suanfa.erchashu;

import java.util.Arrays;
import java.util.Collections;

public class KrusKalAlgorithm {
    public static void main(String[] args) {
        char vertexs[]={ 'A','B','C','D','E','F','G'};
        int size=vertexs.length;
        int edges[][]={{0,7,0,5,0,0,0},{7,0,8,9,7,0,0},{0,8,0,0,5,0,0},{5,9,0,0,15,6,0},{0,7,5,15,0,8,9},{0,0,0,6,8,0,11},{0,0,0,0,9,11,0}};
    Graph graph=new Graph(size);
    KrusKalMinTree krusKalMinTree=new KrusKalMinTree();
  int  edgeNum= krusKalMinTree.createGraph(graph,size,vertexs,edges);
    krusKalMinTree.showGraph(graph);
        System.out.println(Arrays.toString(krusKalMinTree.getEdges(edgeNum,vertexs,edges)));
        //按照权重进行排序
        krusKalMinTree.Kruskal(edgeNum,vertexs,edges);
    }
}
class KrusKalMinTree{
    public int createGraph(Graph graph,int size,char vertexs[],int edges[][]){
        int edgeNum=0;
        //初始化
        for(int i=0;i<size;i++){
            graph.vertex[i]=vertexs[i];
            for(int j=0;j<size;j++){
                graph.edges[i][j]=edges[i][j];
            }
        }
        //找到所有边数
        for(int i=0;i<size;i++){
            for(int j=0;j<size;j++){
                if(edges[i][j]!=0){
                    edgeNum++;
                }
            }
        }
        return edgeNum/2;
    }
    public void showGraph(Graph graph){
        for(int edge[]:graph.edges){
            System.out.println(Arrays.toString(edge));
        }
    }
    //给一个字符，如果找到就返回相应的下标，反之返回-1
    public int getPosition(char ch,char[] vertexs){
        for(int i=0;i<vertexs.length;i++){
            if(vertexs[i]==ch){
                return i;
            }
        }
        return -1;
    }
    public Edge[] getEdges(int edgeNum,char vertexs[],int edges[][]){
        int index=0;
        //存放数组的边
        Edge[] edge=new Edge[edgeNum];
        for(int i=0;i<vertexs.length;i++){
            for(int j=i+1;j<vertexs.length;j++){
                if(edges[i][j]!=0){
                    edge[index++]=new Edge(vertexs[i],vertexs[j],edges[i][j]);
                }
            }
        }
         return edge;
    }
    public int getEnd(int ends[],int i){
        while(ends[i]!=0)
            i=ends[i];
        return i;
    }
    public void Kruskal(int edgeNum,char vertexs[],int edges[][]){
        //当做结果序列的索引
        int index=0;
        //存放结果数组
        Edge[] result=new Edge[edgeNum];
        //存放每个顶点在最小生成树中的终点
        int[] ends=new int[edgeNum];
        //所有边的序列
        Edge[] edges1=getEdges(edgeNum,vertexs,edges);
        Arrays.sort(edges1);
       // System.out.println(Arrays.toString(edges1));
       for(int i=0;i<edgeNum;i++){
           //根据字符找到相应的下标，反之返回-1
           int p1=getPosition(edges1[i].start,vertexs);
           int p2=getPosition(edges1[i].end,vertexs);
           int m=getEnd(ends,p1);    //查看是否被访问过
           int n=getEnd(ends,p2);
           if(m!=n){
               ends[m]=n;                 //将他的结点设置为已经访问过
               result[index++]=edges1[i];

           }

       }
        System.out.println("最小生成树为");
       for(int i=0;i<index;i++){
           System.out.println(result[i]);
       }

    }
}
class Edge implements Comparable<Edge>{
char start;   //边的起始位置
char end;   //边的结束位置
    int weight;    //边的权值
    public Edge(char start, char end, int weight) {
        this.start = start;
        this.end = end;
        this.weight = weight;
    }
    @Override
    public int compareTo(Edge o) {

        return this.weight-o.weight;
    }

    @Override
    public String toString() {
        return "Edge[" +
                "start=" + start +
                ", end=" + end +
                ", weight=" + weight +
                "]\n";
    }
}
